Ο στρατηγός του Βυζαντίου Νικηφόρος Φωκάς απελευθέρωσε την Κρήτη από την Αραβική κατοχή κατά το 961 μ.Χ.. Το Ηράκλειο έπεσε στα χέρια των Βυζαντινών μετά από πολιορκία τεσσάρων μηνών, κατά τη διάρκεια της οποίας οι Άραβες είχαν περίπου 200.000 νεκρούς. Ο Φωκάς έκτισε το Βυζαντινό φρούριο Τέμενο στο Κανλί Καστέλλι και προσπάθησε να μετακινήσει την πόλη του Ηρακλείου εκεί. Η προσπάθειά του δεν πραγματοποιήθηκε και η πόλη παρέμεινε εκεί που ήταν. Ο Χριστιανισμός άνθισε και πάλι, το Ηράκλειο έγινε έδρα του αρχιεπισκόπου ενώ εκκλησίες και μοναστήρια χτίστηκαν σ' όλο το μήκος του νησιού. Πολλές εκκλησίες αυτής της περιόδου σώζονται σε όλο το νησί. Μερικές από τις πιο σημαντικές εκκλησίες είναι: η Παναγιά Κερά στην Κριτσά, ο Μιχαήλ Αρχάγγελος στην Επισκοπή, ο Αϊ Κυρ-Γιάννης στον Αλικιανό, ο Άγιος Νικόλαος στα Κυριακοσέλια, ο 'Αγιος Φανούριος στην Μονή Βαρσαμόνερου, ο Άγιος Παντελεήμωνας στην Πηγή, και ο Άγιος Φανούριος στην Κιθαρίδα. Μερικά από τα πιο σημαντικά μοναστήρια της περιόδου είναι: Μονή Αρκαδίου, Μονή Παλιανής, Μονή Γκουβερνιώτισσα, Μονή Αγίας Τριάδας, Μονή Γκουβερνέτου, Μονή Βροντήσι, Μονή Αγκαράθου, Μονή Τοπλού, Μονή Χαλεπά και Μονή Πρεβέλης.

Την περίοδο αυτή εγκαταστάθηκαν στο νησί οικογένειες ευγενών του Βυζαντίου καθώς και πολλοί από τους στρατιώτες του Νικηφόρου Φωκά, οι οποίοι έχτισαν νέα χωριά.